In a modern cellular system, some modulation schemes are used to transmit several bits at a time, i.e. as a single symbol, as in for example the 8-PSK modulation anticipated to be used in the forthcoming EDGE, i.e. Enhanced Data rates for the Global System for Mobile Communications (GSM) Evolution. The use of such modulation schemes typically results in different error probabilities for the different bits of a symbol. For example, in case of the 8-PSK modulation designed for EDGE, there are three bits transmitted in every symbol (see ETSI (European Telecommunications Standards Institute) specification GSM 05.04, section 3.2, explaining that modulating bits are Gray mapped in groups of three to 8PSK symbols) and the bit error rate (BER) for one of the bits is approximately double compared to the BER for each of the other two bits. In contrast, GSM currently uses the so-called GMSK (Gaussian minimum shift keying) modulation scheme where only one bit is transmitted per symbol and hence the BER for each received bits is the same. An optimum codec (coder/decoder) for a system transmitting several bits per symbol must take into account the uneven BER in multi-bit per symbol modulation schemes because in forward error correction coding, involving convolutional encoding, the bits of the convolutional encoded bit stream do not have even error resilience, i.e. errors in some bits are more critical than errors occurring in other bits.
Special attention should be focused on designing a proper interleaver for the codec of such a system. There are mainly two kinds of interleaver design: a bit interleaver design and a symbol interleaver design. A symbol interleaver interleaves symbols, keeping the bits belonging to each symbol together, while a bit interleaver interleaves an entire bit sequence on bit-per-bit basis.
If a symbol interleaving design is used, the encoded bits would have to be processed according to some algorithm, before the interleaver in order to enhance the error protection performance by controlling the allocation of the bits into symbols. On the other hand, if a bit interleaving design is used, a similar or the same algorithm would again be used, but it would act on the bits after the interleaver.
In prior art systems, a convolutional encoded and possibly punctured bit sequence (a bit sequence where some of the bits, called the punctured bits, have been removed) is interleaved before modulation, as shown in FIGS. 1 and 2. The interleaving operation is vital when convolutional codes are used, because such codes are designed to cope well with random errors but their performance decreases dramatically if the errors are bursty (and if interleaving is not used).
Interleaving ensures that consecutive bits are not sent in the same radio burst and also that neighboring bits in the convolutional encoded sequence are maximally separated within the burst before transmission [see ETSI specification GSM 05.03]. Thus, interleaving tends to ensure that errors occurring in a transmission channel will be distributed as evenly as possible over each entire encoded speech frame, i.e. the errors will appear to be randomly distributed, not bursty. Interleaving is a very common and powerful way to improve error protection performance because most codes are designed to be robust against randomly distributed errors, not bursty errors.
According to the prior art, however, the same kind of interleaving is typically used regardless of the modulation scheme. But when using modulation schemes where the error probability for each bit within a symbol is not even, the interleaving procedure should be adapted to take into account the uneven bit error rate.
One situation where the need to take into account the uneven bit error rate is relevant is in a system using 8-PSK modulation (or any multi-level modulation scheme).
When using a modulation scheme transmitting N bits per symbol, obviously the N-bit symbols must be constructed from the bit sequence before modulation. To do so, the very well known N-bit serial-to-parallel conversion is used. As illustrated in FIGS. 1 and 2, a module 13 performing the N-bit serial-to-parallel conversion is located before the interleaver if a symbol interleaver 14 is used (FIG. 1), and after the interleaver if a bit interleaver 24 is used (FIG. 2). The prior art solution where the conversion is performed after the bit interleaver is described in ETSI specification GSM 05.03 (which sets out in sections 3.11 through 3.13, channel coding for ECSD data channels, i.e. Enhanced Circuit Switched Data, an EDGE version of HSCSD (High Speed Circuit Switched Data) in that ECSD is HSCSD with GMSK modulation changed to 8PSK modulation).
FIG. 5 illustrates the operation of a prior art system where a symbol interleaver is used and serial-to-parallel conversion is located after the interleaver (as in FIG. 1). In the example illustrated in FIG. 5, a 1/3 rate punctured convolutional code is used with 8-PSK modulation (3 bits/symbol). No special actions are taken to control the allocation of convolutional encoded and punctured bits into three-bit symbols. The constructed symbols are fed into the symbol interleaver, which can be based on a block diagonal bit interleaver (as set out in for example GSM 05.03), modified to interleave symbols instead of single bits.
If a symbol interleaver is used in a system, the prior art does guarantee optimal interleaving at the symbol level, but not at the bit level, as can be seen from FIG. 5, where consecutive bits from a puncturing module are transmitted in the same symbol. Such a system leads to more bursty errors for decoding states of the convolutional code, and hence decreases the error protection performance of the code. Such a problem does not occur when using a bit interleaver.
The main non-optimality of the prior art relates to the fact that it does not control the allocation of the encoded bits from a given generator polynomial to a given position within a symbol (if different bit positions within the symbol have different error probabilities, as is usually true). This problem is described below in more detail.
A convolutional encoder, which is usually implemented as a shift register, can be completely described by a connection diagram, such as the connection diagram 110 of FIG. 1A for a rate R=1/2 encoder (2 output bits for every input bit), showing three delay elements 111a, 111b, 111c, and two adders 112, 114. The code rate R is in general written as k/n indicating that the encoder maps a k-tuple to an n-tuple. It is possible to more concisely describe an encoder than by providing a connection diagram. One more concise specification can be given by stating the values of n, k, and the so-called constraint length K (defined in different ways, such as the number of k-tuples that affect the formation of each n-tuple during encoding). For the encoder of FIG. 1A, n=2, k=1, and K=3. Another way is to give the adder connections in the form of vectors or generator polynomials. For example, the rate 1/2 code of FIG. 1A has the generator vectors g1=111 and g2=101, or equivalently, the generator polynomials g1(x)=x2+x+1 and g2(x)=x2+1, where x is the delay. (x implies a delay of one sample, x2 implies a two samples, and so on.
In the example of the encoder illustrated in FIG. 5, the code rate of the 1/3 convolutional code matches perfectly with the number of the bits sent in one symbol, namely three, enabling the allocation of all the bits from one generator polynomial to a certain position within each transmitted symbol, and specifically, allocating the output bits from certain polynomials to strong bit positions and allocating the output bits of other polynomials to weak bit positions. (In 8-PSK modulation, one bit out of the three bits of each symbol has twice the bit error rate as the other two bits. The bit with the higher bit error rate is termed the weak bit, and the other two are called strong bits.) However, if there is any puncturing done after convolutional encoding (as is shown in FIG. 5, and also as in all state of the art channel codecs for speech coding), the allocation of the output bits of the polynomials of the encoder must be made using a more advanced algorithm. It can be seen that at the start of the allocation, the bits from polynomials A and B are allocated to strong bit positions, while bits from polynomial C are allocated to weak bit positions. However, due to puncturing, some bits from polynomials A and B are later allocated to weak bit positions, which is not what is wanted. The unintended allocations reduce the error correction performance of the code, because polynomials A and B in this example are more sensitive to errors in the transmission channel. Whether a polynomial is sensitive is learned by carrying out extensive simulations. (Note that the same problem also arises when the rate of the convolutional code does not match the number of bits to be transmitted as one symbol.)
What is needed is an algorithm, in the case of convolutional encoders that transmit multiple bits per symbol, for separately allocating the bits output by each polynomial of such an encoder into the different positions within a transmitted symbol, an algorithm that takes into account the different error probabilities of the different bits of a symbol provided by such an encoder, so as to improve the error protection performance of the encoder.